package com.moyoutian.sort;

import com.moyoutian.utils.ArrayUtils;

import java.util.Arrays;

/**
 * 快排练习2
 */
public class QuickSort2 {

    public static void main(String[] args) {
//        int[] ints = ArrayUtils.getIntAr(10, 5);
//        int[] ints = new int[]{1, 0, 3, 2, 2, 1, 3, 3, 1, 4};
//        ArrayUtils.printArray("排序前", ints);
//        sort(ints);
//        ArrayUtils.printArray("排序后", ints);
        test();

    }


    /**
     * 测试程序
     */
    public static void test() {
        // 测试次数
        int testCount = 50000;
        for (int i = 0; i < testCount; i++) {
            test(ArrayUtils.getIntAr());
        }
    }

    public static void test(int[] ints) {
        int[] copy_ints_sort = Arrays.stream(ints).sorted().toArray();
        sort(ints);
        if (!Arrays.equals(copy_ints_sort, ints)) {
            System.out.println("QuickSort.test ");
        }
    }

    private static void sort(int[] ints) {
        sortB(ints, 0, ints.length - 1);
    }


    private static void sortB(int[] ints, int left, int right) {
        if (left < right) {
            int temp = ints[right];
            int temp_r = right;
            int temp_l = left;
            while (left < right) {
                while (ints[left] < temp && left < right) {
                    left++;
                }
                while (ints[right] >= temp && left < right) {
                    right--;
                }
                if (left < right) {
                    ArrayUtils.swap(ints, left, right);
                }

            }
            ArrayUtils.swap(ints, right, temp_r);
            sortB(ints, right + 1, temp_r);
            sortB(ints, temp_l, right - 1);
        }

    }


}
